package leetcode.leetcode_417;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    private int [][] DIR = {{0,1},{0,-1},{1,0},{-1,0}};
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        int n = heights.length;
        int m = heights[0].length;
        //  太平洋
        boolean[][] pacific = new boolean[n][m];
        //  左
        for (int i =0;i<n;i++){
            dfs(heights,i,0,pacific);
        }
        //  上
        for (int i = 0;i<m;i++){
            dfs(heights,0,i,pacific);
        }
        //  大西洋
        boolean[][] atlantic = new boolean[n][m];
//        右
        for (int i =0;i<n;i++){
            dfs(heights,i,m-1,atlantic);
        }
//        下
        for (int i = 0;i<m;i++){
            dfs(heights,n-1,i,atlantic);
        }
        List<List<Integer>> list = new ArrayList<>();
        for (int i =0;i<n;i++){
            for (int j =0;j<m;j++){
               if (pacific[i][j]&&atlantic[i][j]){
                   list.add(new ArrayList<>(Arrays.asList(i,j)));
               }

            }
        }
        return list;

    }
    private void dfs(int[][] heights , int i ,int j ,boolean [][] visited){
        if (visited[i][j]){
            return;
        }
        visited[i][j] = true;
        for (int [] dir:DIR){
            int x = i +dir[0];
            int y = j +dir[1];
            if (x>=0&&x<heights.length&&y>=0&&y<heights[0].length&&heights[x][y]>=heights[i][j]){
                dfs(heights,x,y,visited);
            }
        }

    }
}